// Components for manipulating sequences of characters -*- C++ -*-

// Copyright (C) 1997-2013 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/** @file bits/basic_string.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{string}

 */

//

// ISO C++ 14882: 21 Strings library

//

#ifndef _BASIC_STRING_H

#define _BASIC_STRING_H 1

#pragma GCC system_header

#include <ext/atomicity.h>

#include <debug/debug.h>

#if __cplusplus >= 201103L

#include <initializer_list>

#endif

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**

   *  @class basic_string basic_string.h <string>

   *  @brief  Managing sequences of characters and character-like objects.

   *

   *  @ingroup strings

   *  @ingroup sequences

   *

   *  @tparam _CharT  Type of character

   *  @tparam _Traits  Traits for character type, defaults to

   *                   char_traits<_CharT>.

   *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.

   *

   *  Meets the requirements of a <a href="tables.html#65">container</a>, a

   *  <a href="tables.html#66">reversible container</a>, and a

   *  <a href="tables.html#67">sequence</a>.  Of the

   *  <a href="tables.html#68">optional sequence requirements</a>, only

   *  @c push_back, @c at, and @c %array access are supported.

   *

   *  @doctodo

   *

   *

   *  Documentation?  What's that?

   *  Nathan Myers <ncm@cantrip.org>.

   *

   *  A string looks like this:

   *

   *  @code

   *                                        [_Rep]

   *                                        _M_length

   *   [basic_string<char_type>]            _M_capacity

   *   _M_dataplus                          _M_refcount

   *   _M_p ---------------->               unnamed array of char_type

   *  @endcode

   *

   *  Where the _M_p points to the first character in the string, and

   *  you cast it to a pointer-to-_Rep and subtract 1 to get a

   *  pointer to the header.

   *

   *  This approach has the enormous advantage that a string object

   *  requires only one allocation.  All the ugliness is confined

   *  within a single %pair of inline functions, which each compile to

   *  a single @a add instruction: _Rep::_M_data(), and

   *  string::_M_rep(); and the allocation function which gets a

   *  block of raw bytes and with room enough and constructs a _Rep

   *  object at the front.

   *

   *  The reason you want _M_data pointing to the character %array and

   *  not the _Rep is so that the debugger can see the string

   *  contents. (Probably we should add a non-inline member to get

   *  the _Rep for the debugger to use, so users can check the actual

   *  string length.)

   *

   *  Note that the _Rep object is a POD so that you can have a

   *  static <em>empty string</em> _Rep object already @a constructed before

   *  static constructors have run.  The reference-count encoding is

   *  chosen so that a 0 indicates one reference, so you never try to

   *  destroy the empty-string _Rep object.

   *

   *  All but the last paragraph is considered pretty conventional

   *  for a C++ string implementation.

  */

  // 21.3  Template class basic_string

  template<typename _CharT, typename _Traits, typename _Alloc>

    class basic_string

    {

      typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;

      // Types:

    public:

      typedef _Traits					    traits_type;

      typedef typename _Traits::char_type		    value_type;

      typedef _Alloc					    allocator_type;

      typedef typename _CharT_alloc_type::size_type	    size_type;

      typedef typename _CharT_alloc_type::difference_type   difference_type;

      typedef typename _CharT_alloc_type::reference	    reference;

      typedef typename _CharT_alloc_type::const_reference   const_reference;

      typedef typename _CharT_alloc_type::pointer	    pointer;

      typedef typename _CharT_alloc_type::const_pointer	    const_pointer;

      typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;

      typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>

                                                            const_iterator;

      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

      typedef std::reverse_iterator<iterator>		    reverse_iterator;

    private:

      // _Rep: string representation

      //   Invariants:

      //   1. String really contains _M_length + 1 characters: due to 21.3.4

      //      must be kept null-terminated.

      //   2. _M_capacity >= _M_length

      //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).

      //   3. _M_refcount has three states:

      //      -1: leaked, one reference, no ref-copies allowed, non-const.

      //       0: one reference, non-const.

      //     n>0: n + 1 references, operations require a lock, const.

      //   4. All fields==0 is an empty string, given the extra storage

      //      beyond-the-end for a null terminator; thus, the shared

      //      empty string representation needs no constructor.

      struct _Rep_base

      {

	size_type		_M_length;

	size_type		_M_capacity;

	_Atomic_word		_M_refcount;

      };

      struct _Rep : _Rep_base

      {

	// Types:

	typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;

	// (Public) Data members:

	// The maximum number of individual char_type elements of an

	// individual string is determined by _S_max_size. This is the

	// value that will be returned by max_size().  (Whereas npos

	// is the maximum number of bytes the allocator can allocate.)

	// If one was to divvy up the theoretical largest size string,

	// with a terminating character and m _CharT elements, it'd

	// look like this:

	// npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)

	// Solving for m:

	// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1

	// In addition, this implementation quarters this amount.

	static const size_type	_S_max_size;

	static const _CharT	_S_terminal;

	// The following storage is init'd to 0 by the linker, resulting

        // (carefully) in an empty string with one reference.

        static size_type _S_empty_rep_storage[];

        static _Rep&

        _S_empty_rep()

        { 

	  // NB: Mild hack to avoid strict-aliasing warnings.  Note that

	  // _S_empty_rep_storage is never modified and the punning should

	  // be reasonably safe in this case.

	  void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);

	  return *reinterpret_cast<_Rep*>(__p);

	}

        bool

	_M_is_leaked() const

        { return this->_M_refcount < 0; }

        bool

	_M_is_shared() const

        { return this->_M_refcount > 0; }

        void

	_M_set_leaked()

        { this->_M_refcount = -1; }

        void

	_M_set_sharable()

        { this->_M_refcount = 0; }

	void

	_M_set_length_and_sharable(size_type __n)

	{

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	  if (__builtin_expect(this != &_S_empty_rep(), false))

#endif

	    {

	      this->_M_set_sharable();  // One reference.

	      this->_M_length = __n;

	      traits_type::assign(this->_M_refdata()[__n], _S_terminal);

	      // grrr. (per 21.3.4)

	      // You cannot leave those LWG people alone for a second.

	    }

	}

	_CharT*

	_M_refdata() throw()

	{ return reinterpret_cast<_CharT*>(this + 1); }

	_CharT*

	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)

	{

	  return (!_M_is_leaked() && __alloc1 == __alloc2)

	          ? _M_refcopy() : _M_clone(__alloc1);

	}

	// Create & Destroy

	static _Rep*

	_S_create(size_type, size_type, const _Alloc&);

	void

	_M_dispose(const _Alloc& __a)

	{

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	  if (__builtin_expect(this != &_S_empty_rep(), false))

#endif

	    {

	      // Be race-detector-friendly.  For more info see bits/c++config.

	      _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);

	      if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,

							 -1) <= 0)

		{

		  _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);

		  _M_destroy(__a);

		}

	    }

	}  // XXX MT

	void

	_M_destroy(const _Alloc&) throw();

	_CharT*

	_M_refcopy() throw()

	{

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	  if (__builtin_expect(this != &_S_empty_rep(), false))

#endif

            __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);

	  return _M_refdata();

	}  // XXX MT

	_CharT*

	_M_clone(const _Alloc&, size_type __res = 0);

      };

      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html

      struct _Alloc_hider : _Alloc